package data_structure

import (
	"fmt"
	"sync"
)

type Bag struct {
	pennantList       []*Pennant
	putLock           sync.Mutex
	hopper            *Pennant
	currentHopperSize int
}

const (
	PennantSlotMaxSize  int = 33
	HopperMaxSize       int = 16
	InsertStartPosition int = 4
)

func NewBag() *Bag {
	return &Bag{
		pennantList:       make([]*Pennant, PennantSlotMaxSize),
		putLock:           sync.Mutex{},
		currentHopperSize: 0,
	}
}

// 带有缓冲的插入操作
func (b *Bag) InsertWithHopper(v int32) {
	newPennant := NewPennant(v)
	b.putLock.Lock()
	defer b.putLock.Unlock()
	if b.hopper == nil {
		// 如果当前缓冲区为空，直接设置缓冲区根节点为当前节点
		b.hopper = newPennant
		b.currentHopperSize++
	} else {
		b.hopper = b.hopper.Union(newPennant)
		b.currentHopperSize++
		if b.currentHopperSize == HopperMaxSize {
			// 如果达到了缓冲区最大值，那么就要注入到bag中
			k := InsertStartPosition
			for b.pennantList[k] != nil && k < PennantSlotMaxSize {
				target := b.pennantList[k]
				b.hopper = target.Union(b.hopper)
				b.pennantList[k] = nil
				k++
			}
			b.pennantList[k] = b.hopper
			b.hopper = nil
			b.currentHopperSize = 0
		}
	}
}

func (b *Bag) Insert(v int32) {
	newPennant := NewPennant(v)
	b.putLock.Lock()
	defer b.putLock.Unlock()
	k := 0
	for b.pennantList[k] != nil && k != PennantSlotMaxSize {
		target := b.pennantList[k]
		newPennant = target.Union(newPennant)
		b.pennantList[k] = nil
		k++
	}
	b.pennantList[k] = newPennant
}

func (b *Bag) Travel() {
	totalNum := 0
	count := 0
	for i := 0; i < PennantSlotMaxSize; i++ {
		if b.pennantList[i] == nil {
			fmt.Println(0)
			continue
		}
		count = 0
		b.doTravel(b.pennantList[i], &count)
		totalNum += count
		fmt.Println(count)
	}
	fmt.Println(totalNum)
}

func (b *Bag) doTravel(pennant *Pennant, count *int) {
	if pennant == nil {
		return
	}
	*count++
	b.doTravel(pennant.Left, count)
	b.doTravel(pennant.Right, count)
	return
}
